n=500;
u=[1,3,4,5,5,1,3,4,8,1,1,13,14,15,1,9,14,3,20,21,2,17,24,23,17,23,18,29,2,12,32,2,33,35,23,37,38,39,40,41,13,9,14,45,46,35,48,46,33,51,52,53,54,48,56,29,58,1,60,61,62,26,43,65,66,60,68,49,66,46,67,73,74,39,76,77,78,79,65,81,70,83,46,85,86,87,34,89,14,91,92,88,9,95,96,75,98,99,100,71,102,77,104,36,106,107,108,65,110,84,19,60,114,31,116,21,118,119,118,121,69,123,69,125,97,127,128,129,130,56,24,49,14,124,20,137,138,139,140,141,142,125,95,145,146,147,93,149,150,33,3,66,154,1,156,77,74,80,60,161,162,118,144,40,166,42,168,137,170,116,172,173,113,139,176,42,14,129,102,181,137,173,184,159,186,14,188,157,190,57,1,70,194,195,196,197,62,52,182,168,202,203,177,205,206,207,208,66,145,91,174,213,54,215,216,110,37,167,28,138,187,223,141,225,156,96,30,21,15,231,232,93,233,235,236,237,238,58,39,241,50,243,10,245,246,247,95,175,250,251,252,253,254,255,256,257,243,72,33,261,235,29,264,265,116,142,61,205,270,271,272,47,51,275,276,59,188,236,280,281,201,283,284,169,180,287,249,288,290,291,292,293,163,295,296,257,2,299,207,299,101,303,304,227,62,307,7,309,310,141,312,313,314,315,88,284,318,319,320,321,161,323,52,118,91,327,319,183,216,76,75,133,334,222,336,283,338,92,340,341,132,217,344,345,346,347,348,40,350,17,31,165,354,355,339,357,190,248,187,196,289,363,64,77,366,238,368,369,324,217,372,373,345,258,339,6,378,379,380,229,382,383,384,192,77,387,388,119,390,370,392,393,394,126,396,397,398,399,101,69,402,379,404,262,406,54,156,409,410,411,214,413,414,372,416,417,267,37,63,121,198,423,214,425,426,427,428,102,430,431,432,73,207,58,436,437,438,277,440,441,442,443,444,445,446,447,157,188,335,349,452,258,454,455,316,457,440,293,460,461,462,193,434,465,466,126,468,35,470,339,414,473,224,475,131,477,478,177,99,206,24,81,484,485,9,231,261,423,490,491,289,493,180,292,11,178,322,274,442];
v=[2,1,2,1,6,7,8,9,10,11,12,1,2,6,16,17,18,19,14,3,22,23,16,25,26,27,28,14,30,31,5,33,34,13,36,34,31,17,39,6,42,43,44,33,15,47,34,49,50,42,41,18,21,55,40,57,48,59,59,3,35,63,64,7,8,67,28,69,70,71,72,46,23,75,63,40,15,24,80,39,82,55,84,48,30,84,88,37,90,10,33,93,94,18,45,97,82,37,56,101,20,103,55,105,43,66,31,109,37,111,112,113,53,115,79,117,45,104,120,62,122,71,124,90,126,107,80,71,90,131,132,133,134,135,136,23,115,46,132,87,45,143,144,133,110,128,148,85,121,151,152,153,55,155,148,157,158,159,160,83,144,163,164,165,6,167,165,169,29,171,158,89,174,175,165,177,178,179,180,123,182,183,17,185,71,187,169,189,102,191,192,193,78,5,40,23,198,199,200,201,67,145,204,48,58,30,189,209,210,211,212,16,214,71,14,217,218,219,220,221,222,44,224,90,226,227,228,229,230,60,86,233,234,47,235,84,213,239,240,23,242,238,244,112,49,227,248,249,113,227,92,119,96,142,254,197,258,259,260,41,262,263,239,88,266,267,268,269,134,93,90,273,274,185,112,277,278,279,10,2,282,278,265,285,286,254,288,289,284,283,15,204,294,213,87,297,298,37,300,301,302,84,236,305,306,137,308,188,112,311,256,255,298,138,316,317,174,117,74,195,322,320,324,325,326,35,328,329,330,331,332,333,169,335,54,337,137,339,134,321,342,343,135,229,118,236,139,349,74,351,352,353,95,214,356,355,358,359,360,361,362,347,364,365,255,367,241,158,370,371,313,188,374,375,376,377,266,63,376,381,292,362,14,385,386,167,36,389,61,391,1,390,207,395,63,117,361,194,400,401,41,403,274,405,129,407,408,160,130,364,412,378,155,415,153,10,418,419,420,421,422,296,424,190,308,398,159,429,384,178,49,433,434,435,271,163,243,439,4,420,264,306,102,217,122,317,448,449,450,451,32,453,97,415,456,172,458,459,218,355,244,463,464,416,225,467,73,469,322,471,472,393,474,377,476,180,460,479,480,481,482,483,288,34,486,487,488,489,441,84,492,98,494,495,496,497,498,499,500];
w=[24167,1774,4769,11790,19265,26115,3207,15064,16988,5502,24122,25590,7601,26150,3538,6693,31256,32229,13744,5504,9257,11412,8952,28273,1877,1032,23633,14299,31556,32604,3291,1668,2928,17792,3953,4552,5378,21250,5664,22907,22251,5915,10726,32030,20550,20476,32431,12357,2285,12890,22412,30791,8281,10295,30517,7975,16063,13042,22721,1986,17511,15504,11427,20282,21326,25676,21992,26530,3839,4701,25518,6122,11950,24327,17127,3340,15766,6373,9295,26743,9619,30324,21163,30651,24578,16097,30019,374,26840,30231,31393,21374,20481,22531,10123,32335,1274,12074,1597,27062,14513,21102,12779,11966,29084,22043,14966,25306,11800,15416,7276,16468,12547,12299,2373,22517,21660,6381,31708,14325,32665,4176,21803,13348,6281,1805,32075,15193,4972,9714,17578,26139,30096,13707,397,10894,27566,6447,9673,24991,20036,10574,18621,2418,12340,30969,24979,28939,21406,21170,11703,14652,8442,30837,32662,22222,31864,29445,29083,498,5531,31867,14694,16105,3347,21005,5966,27634,3291,31003,7705,116,11923,17279,20218,26988,19487,7956,17867,12056,5760,31879,29067,20451,3826,22877,5402,31891,15941,14661,3123,8625,18048,6815,4265,27193,10931,12875,31717,10115,26908,31414,16543,19056,17277,25122,6363,22999,20924,9270,9254,4657,15035,6853,29202,6787,12153,4578,13551,31372,1129,27427,6347,15919,1298,7220,31403,29218,24040,21663,31754,26071,14440,22234,11921,24235,25977,20625,21528,10317,12802,15925,28381,11888,16839,9668,7683,2995,3208,13530,589,14799,22876,3576,10011,20227,21578,20755,11172,29884,6697,11103,10357,905,22200,31325,3369,28733,20736,20002,29289,30309,489,22249,7207,11244,4379,2524,10262,27147,21527,2334,9324,14199,11157,6939,2779,8133,23327,15636,23500,9248,14062,7396,21981,12590,17412,1560,1437,17983,9866,3630,10630,14775,31339,3116,9787,18109,29232,10084,1795,20516,22557,2438,18052,1177,19853,32742,23491,20494,25738,6158,18267,18021,28592,902,7420,29536,9283,20195,17703,15304,27278,14349,29480,15324,30845,12245,2899,20220,4733,21174,30082,11413,3731,25833,6093,17999,30139,7599,30091,21364,24451,19930,11913,13731,25575,11677,23177,8886,16238,23957,31998,16368,1412,26391,3333,6763,32026,18363,19878,10432,891,21544,29259,16886,4465,32289,19328,13744,16024,18895,30700,29074,24321,32337,21903,24563,5898,23937,12093,27593,380,28424,25178,21968,17381,10916,30934,18172,11576,3511,29547,19489,15010,26643,16406,9952,7854,27652,6355,8148,9883,19870,18076,17917,6653,32073,1187,18284,28818,18825,32718,20271,31334,29714,11891,5247,22057,1547,31828,1832,20943,28577,1756,17719,4457,16079,26011,17898,6210,31083,15103,26068,4157,26228,2389,16463,27502,21146,2046,550,15350,7183,29941,8578,24099,4492,7808,10005,20679,28837,8501,29829,22488,3921,5680,13339,17737,31923,11666,23980,1063,9518,28989,31943,16886,17833,11213,9247,21069,14878,12249,14906,10415,29545,31594,2906,1196,8270,29627,19627,11320,21962,13619,31918,20555,17054,13215];
m=100;
army=[100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100];